import sun.reflect.generics.tree.Tree;

import java.util.*;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: xiaotutu
 * Date: 2024-10-21
 * Time: 13:05
 */
public class BinaryTree {
    public static class TreeNode {
        public int val;
        public TreeNode left;
        public TreeNode right;

        public TreeNode(int val) {
           this.val = val;
        }
    }


    public static TreeNode createTree() {
        TreeNode node1 = new TreeNode(1);
        TreeNode node2 = new TreeNode(2);
        TreeNode node3 = new TreeNode(3);
        TreeNode node4 = new TreeNode(4);
        TreeNode node5 = new TreeNode(5);
        TreeNode node6 = new TreeNode(6);
        TreeNode node7 = new TreeNode(7);
        TreeNode node8 = new TreeNode(8);
        node1.left = node2;
        node1.right = node3;
        node2.left =  node4 ;
        node2.right = node5;
        node3.left = node6;
        node3.right = node7;
        node5.right = node8;
        return node1;
    }
    // 前序遍历
    public static void preOrder(TreeNode root) {
        if(root == null) return;
        System.out.print(root.val + " ");
        preOrder(root.left);
        preOrder(root.right);
    }

    // 前序遍历(有返回值的写法)
    public static List<Integer> preOrder2(TreeNode root) {
        List<Integer> ret = new ArrayList<>();
        if(root == null) return ret;
        ret.add(root.val);
        List<Integer> leftTree = preOrder2(root.left);
        ret.addAll(leftTree);
        List<Integer> rightTree = preOrder2(root.right);
        ret.addAll(rightTree);
        return ret;
    }
    // 中序遍历(有返回值的写法)
    public static List<Integer> inOrder(TreeNode root) {
        List<Integer> ret = new ArrayList<>();
        if(root == null) return ret;
        List<Integer> leftTree = inOrder(root.left);
        ret.addAll(leftTree);
        ret.add(root.val);
        List<Integer> rightTree = inOrder(root.right);
        ret.addAll(rightTree);
        return ret;
    }

    // 后序遍历(有返回值的写法)
    public static List<Integer> postOrder(TreeNode root) {
        List<Integer> ret = new ArrayList<>();
        if(root == null) return ret;
        List<Integer> leftTree = postOrder(root.left);
        ret.addAll(leftTree);
        List<Integer> rightTree = postOrder(root.right);
        ret.addAll(rightTree);
        ret.add(root.val);
        return ret;
    }

    // 获取树中节点的个数
    public static int size(TreeNode root) {
        if(root == null) {
            return 0;
        }
        return size(root.left) + size(root.right) + 1;
    }
    // 获取叶子节点的个数
    public static int getLeafCount(TreeNode root) {
        if(root == null) {
            return 0;
        }
        if(root.left == null && root.right == null) {
            return 1;
        }
        return getLeafCount(root.left) + getLeafCount(root.right);
    }

    // 获取第K层节点的个数
    public static int getKLevelNodeCount(TreeNode root, int k) {
        if(root == null) {
            return 0;
        }
        if(k == 1) {
            return 1;
        }
        return getKLevelNodeCount(root.left, k-1) + getKLevelNodeCount(root.right, k-1);

    }

    // 获取二叉树的高度
    public static int getHeight(TreeNode root) {
        if(root == null) {
            return 0;
        }
        int leftH = getHeight(root.left);
        int rightH = getHeight(root.right);
        return (leftH > rightH ? leftH : rightH) + 1;
    }

    // 检测值为value的元素是否存在
    public static TreeNode find(TreeNode root, int val) {
        if(root == null) return null;
        if(root.val == val) {
            return root;
        }
        TreeNode leftVal = find(root.left, val);
        if(leftVal != null) {
            return leftVal;
        }
        TreeNode rightVal = find(root.right, val);
        if(rightVal != null) {
            return rightVal;
        }
        return null;
    }

    //层序遍历
    public static void levelOrder(TreeNode root) {
        Queue<TreeNode> queue = new LinkedList<>();
        if(root != null) {
            queue.offer(root);
        }
        while(!queue.isEmpty()) {
            TreeNode top = queue.poll();
            System.out.print(top.val + " ");
            if(top.left != null) {
                queue.offer(top.left);
            }
            if(top.right != null) {
                queue.offer(top.right);
            }
        }
    }

    public List<List<Integer>> levelOrder2(TreeNode root) {
        Queue<TreeNode> queue = new LinkedList<>();
        if(root != null) {
            queue.offer(root);
        }
        List<List<Integer>> ret = new ArrayList<>();
        while(!queue.isEmpty()) {
            List<Integer> list = new ArrayList<>();
            int size = queue.size();
            while(size != 0) {
                TreeNode top = queue.poll();
                list.add(top.val);
                if(top.left != null) {
                    queue.offer(top.left);
                }
                if(top.right != null) {
                    queue.offer(top.right);
                }
                size--;
            }
            ret.add(list);
        }
        return ret;
    }
    // 判断一棵树是不是完全二叉树
    public static boolean isCompleteTree(TreeNode root) {
        Queue<TreeNode> queue = new LinkedList<>();
        if(root != null) {
            queue.offer(root);
        }
        while(!queue.isEmpty()) {
            TreeNode top = queue.poll();
            if(top == null) {
                break;
            }
            queue.offer(top.left);
            queue.offer(top.right);
        }
        while(!queue.isEmpty()) {
            TreeNode top = queue.poll();
            if(top != null) {
                return false;
            }
        }
        return true;
    }
    // 判断是否为相同的树
    public static boolean isSameTree(TreeNode p, TreeNode q) {
        if(p == null && q == null) {
            return true;
        }
        if(p != null && q == null || p == null && q != null) {
            return false;
        }
        if(p.val != q.val) {
            return false;
        }
        return isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
    }
    // 判断另一棵树的子树

    public static boolean isSubtree(TreeNode root, TreeNode subRoot) {
        if(root == null) return false;
        if(isSameTree(root, subRoot)) {
            return true;
        }
        if(isSubtree(root.left, subRoot)) {
            return true;
        }
        if(isSubtree(root.right, subRoot)) {
            return true;
        }
        return false;
    }
    // 翻转二叉树
    public TreeNode invertTree(TreeNode root) {
        if(root == null) return null;
        TreeNode tmp = root.left;
        root.left = root.right;
        root.right = tmp;
        invertTree(root.left);
        invertTree(root.right);
        return root;
    }
    // 判断一棵树是不是平衡二叉树
    public boolean isBalanced(TreeNode root) {
        if(root == null) return true;
        int leftH = getHeight(root.left);
        int rightH = getHeight(root.right);
        return Math.abs(leftH - rightH) < 2 && isBalanced(root.left) && isBalanced(root.right);
    }

    public static int getHeight2(TreeNode root) {
        if(root == null) {
            return 0;
        }
        int leftH = getHeight(root.left);
        int rightH = getHeight(root.right);
        if(Math.abs(leftH - rightH) > 1 && leftH >=0 && rightH >= 0) {
            return -1;
        }else {
            return Math.max(leftH, rightH) + 1;
        }
    }

    public boolean isSymmetric(TreeNode root) {
        if(root == null) return true;
        return isSymmetricChild(root.left, root.right);
    }

    public boolean isSymmetricChild(TreeNode leftTree, TreeNode rightTree) {
        if(leftTree == null && rightTree == null) {
            return true;
        }
        if(leftTree != null && rightTree == null || leftTree == null && rightTree != null) {
            return false;
        }
        if(leftTree.val != rightTree.val) {
            return false;
        }
        return isSymmetricChild(leftTree.left,rightTree.right) &&
                isSymmetricChild(leftTree.right, rightTree.left);
    }



    public TreeNode lowestCommonAncestor2(TreeNode root, TreeNode p, TreeNode q) {
        if(root == null) return null;

        Stack<TreeNode> s1 = new Stack<>();
        getPath(root,p,s1);

        Stack<TreeNode> s2 = new Stack<>();
        getPath(root,q,s2);

        int size1 = s1.size();
        int size2 = s2.size();

        if(size1 > size2) {
            int size = size1 - size2;
            while (size != 0) {
                s1.pop();
                size--;
            }
        }else {
            int size = size2 - size1;
            while (size != 0) {
                s2.pop();
                size--;
            }
        }
        //两个栈当中 的元素 是一样大小的
        while (!s1.empty() && !s2.empty()) {
            TreeNode tmp1 = s1.pop();
            TreeNode tmp2 = s2.pop();
            if(tmp1 == tmp2) {
                return tmp1;
            }
        }
        return null;
    }

    /**
     * 在root这棵树当中 找到node这个节点上的位置
     * @param root
     * @param node
     * @return
     */
    public boolean getPath(TreeNode root, TreeNode node, Stack<TreeNode> stack) {
        if(root == null) {
            return false;
        }
        stack.push(root);
        if(root == node) {
            return true;
        }
        boolean ret = getPath(root.left,node,stack);
        if(ret == true) {
            return true;
        }

        boolean ret2 = getPath(root.right,node,stack);
        if(ret2 == true) {
            return true;
        }
        stack.pop();
        return false;
    }

    public void preOrderNor(TreeNode root) {
        if(root == null) return;
        Stack<TreeNode> stack = new Stack<>();
        TreeNode cur = root;

        while (cur != null || !stack.empty()) {
            while (cur != null) {
                stack.push(cur);
                System.out.print(cur.val + " ");
                cur = cur.left;
            }
            //cur == null
            TreeNode top = stack.pop();
            cur = top.right;
        }
    }

    public static void main(String[] args) {
        TreeNode root = createTree();
        List<Integer> ret = preOrder2(root);
        System.out.println(ret);
//        System.out.println(size(root));
//        System.out.println(getLeafCount(root));
//        System.out.println(getKLevelNodeCount(root, 4));
//        System.out.println(getHeight(root));
//        System.out.println(find(root, 6).val);
//        levelOrder(root);
//        System.out.println(isCompleteTree(root));
    }
}
